/*
 * @lc app=leetcode.cn id=347 lang=cpp
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //先统计每个数出现了多少次
        //进行统计汇总
        //计数排序
        //统计数组
        // 0 1 2 3 4 5 6
        // x x x x x x x
        //分别代表出现num次数的个数x
        //遍历从大到小找到分界点(出现K次)

        unordered_map<int, int> cnt;
        for(auto x : nums) cnt[x]++;

        vector<int> s(nums.size() + 1, 0);
        for(auto [x, c] : cnt) s[c]++;

        int fenjie = nums.size(), sum = 0;
        while(sum < k){
            sum += s[fenjie--];
        }

        vector<int> ans;
        for(auto [x, c] : cnt)
            if(c > fenjie) ans.push_back(x);

        return ans;
    }
};
// @lc code=end

